package Midium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//39.组合总和
//别看了，下面都是错的
//难点，数组中的数可以被使用任意次
public class Solution39 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> resList = new ArrayList<>();
        int index;
        //首先找到距离target最近的较大值或者target本身，从它-1开始对数组前面的元素进行遍历
        for (index = 0; index < candidates.length; index++) {
            if (candidates[index] == target) {
                List<Integer> list = new ArrayList<>();
                list.add(target);
                resList.add(list);
                break;
            } else if (candidates[index] > target) {
                break;
            }
        }
        for (int i = index - 1; i >= 0; i--) {
            //index对应的元素可能是由i对应的数的n倍+tar(新的target的简称)决定的
            for (int k = 1; k * candidates[i] <= target; k++) {
                List<Integer> list = new ArrayList<>();
                int old = k * candidates[i];
                //先放入k个candidates[i]
                for (int j = 0; j < k; j++) {
                    list.add(candidates[i]);
                }
                if (old == target) {
                    resList.add(list);
                } else {
                    //寻找target-old
                    int r = find(candidates, target - old, list, i, resList);
                    //如果r==target-old，说明list里面没有-1
                    if (r == target - old) {
                        resList.add(list);
                    }
                }
            }
        }
        return resList;
    }

    //从arr[0,right)里找一个新的target，使得新的target+当前数==target，返回值为新的target
    //找不到则返回-1
    public static int find(int[] arr, int target, List<Integer> list, int right, List<List<Integer>> resList) {
        //首先找到距离target最近的较大值或者target本身，从它-1开始对数组前面的元素进行遍历
        int index;
        boolean firstT = false;
        for (index = 0; index < right; index++) {
            if (arr[index] == target) {
                list.add(target);
                resList.add(list);
                firstT = true;
                //注意：此时虽然找到了满足的数，但是这个数也有可能是比它更小的多个数组成
                //这两种情况都要加入resList
                //但是也有可能不存在比它更小的多个数组成，避免错误的返回-1，所以引入firstT
                //因为list是指针，所以不能直接remove
                list = new ArrayList<>(list);
                list.remove((Integer) target);
                break;

            } else if (arr[index] > target) {
                break;
            }
        }
        for (int i = index - 1; i >= 0; i--) {
            //index对应的元素可能是由i对应的数的n倍+tar(新的target的简称)决定的
            for (int k = 1; k * arr[i] <= target; k++) {
                int old = k * arr[i];
                //先放入k个arr[i]
                for (int j = 0; j < k; j++) {
                    list.add(arr[i]);
                }
                if (old == target) {
                    resList.add(list);
                    return target;
                } else {
                    //寻找target-old
                    int r = find(arr, target - old, list, i, resList);
                    //如果r==target-old，说明list里面没有-1
                    if (r == target - old) {
                        resList.add(list);
                        return r;
                    } else if (r == -1) {
                        //移除list里放入的那个数
                        for (int j = 0; j < k; j++) {
                            list.remove((Integer) arr[i]);
                        }
                    }
                }
            }
        }
        if (firstT)
            return target;
        return -1;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum(new int[]{1,2,6}, 9);
        for (List<Integer> list : lists) {
            System.out.print("[");
            for (int i : list) {
                System.out.print(i + ",");
            }
            System.out.flush();
            System.out.println("],");
        }
    }
}
